package 数据结构练习.summer;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class day16 {
    /*
    请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
    实现 MyStack 类：
    void push(int x) 将元素 x 压入栈顶。
    int pop() 移除并返回栈顶元素。
    int top() 返回栈顶元素。
    boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
    https://leetcode.cn/problems/implement-stack-using-queues
     */

    Queue<Integer> s1, s2;

    public day16() {
        s1 = new LinkedList<>();
        s2 = new LinkedList<>();
    }

    public void push(int x) {
        //哪边有值就存到哪边,都为空就存到s1
        if (!s2.isEmpty()) {
            s2.add(x);
        } else {
            s1.add(x);
        }
    }

    public int pop() {
        if (empty()) return -1;
        //s2为空就把s1的元素弹出添加到s2但要保留一个元素,最后保留的元素作为删除元素,s1为空反之
        int size1 = s1.size();
        int size2 = s2.size();
        if (s2.isEmpty()) {
            for (int i = 1; i < size1; i++) {
                s2.add(s1.poll());
            }
            return s1.poll();
        } else {
            for (int i = 1; i < size2; i++) {
                s1.add(s2.poll());
            }
            return s2.poll();
        }
    }

    public int top() {
        if (empty()) return -1;
        //s2为空就把s1的元素弹出添加到s2但要保留一个元素,最后保留的元素作为弹出元素,s1为空反之
        int size1 = s1.size();
        int size2 = s2.size();
        if (s2.isEmpty()) {
            for (int i = 1; i < size1; i++) {
                s2.add(s1.poll());
            }
            int temp = s1.peek();
            s2.add(s1.poll());
            return temp;
        } else {
            for (int i = 1; i < size2; i++) {
                s1.add(s2.poll());
            }
            int temp = s2.peek();
            s1.add(s2.poll());
            return temp;
        }
    }

    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }


}

/*
   请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
   实现 MyQueue 类：
   void push(int x) 将元素 x 推到队列的末尾
   int pop() 从队列的开头移除并返回元素
   int peek() 返回队列开头的元素
   boolean empty() 如果队列为空，返回 true ；否则，返回 false
   https://leetcode.cn/problems/implement-queue-using-stacks
 */
class MyQueue {
    //t1存元素t2出元素
    Stack<Integer> t1, t2;
    public MyQueue() {
        t1 = new Stack<>();
        t2 = new Stack<>();
    }

    public void push(int x) {
        t1.add(x);
    }

    public int pop() {
        if(empty())return -1;
        if(!t2.empty()){
            return t2.pop();
        }else{
            while(!t1.empty()){
                t2.add(t1.pop());
            }
            return t2.pop();
        }
    }

    public int peek() {
        if(empty())return -1;
        if(!t2.empty()){
            return t2.peek();
        }else{
            while(!t1.empty()){
                t2.add(t1.pop());
            }
            return t2.peek();
        }
    }

    public boolean empty() {
        return t1.empty()&&t2.empty();
    }
}